{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../../img/ods_stickers.jpg\">\n",
    "## Открытый курс по машинному обучению\n",
    "</center>\n",
    "Автор материала: программист-исследователь Mail.ru Group, старший преподаватель Факультета Компьютерных Наук ВШЭ Юрий Кашницкий. Материал распространяется на условиях лицензии [Creative Commons CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/). Можно использовать в любых целях (редактировать, поправлять и брать за основу), кроме коммерческих, но с обязательным упоминанием автора материала."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center>Тема 8. Стохастический градиентный спуск, онлайн-обучение, Vowpal Wabbit</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Всем привет! Вот мы постепенно и дошли до продвинутых методов машинного обучения, сегодня обсудим, как вообще подступиться к обучению модели, если данных гигабайты и десятки гигабайт.\n",
    "Обсудим приемы, позволяющие это делать: стохастический градиентный спуск (SGD) и хэширование признаков, посмотрим на примеры применения библиотеки Vowpal Wabbit. Домашнее задание будет как на реализацию SGD-алгоритмов, так и на обучение классификатора вопросов на StackOverflow по выборке в 10 Гб. \n",
    "\n",
    "Поехали!\n",
    "\n",
    "# План\n",
    "- Стохастический градиентный спуск и онлайн-подход к обучению\n",
    "    - Стохастический градиентный спуск\n",
    "    - Онлайн-подход к обучению\n",
    "- Работа с категориальными признаками: Label Encoding, One-Hot Encoding, Hashing trick\n",
    "    - Label Encoding\n",
    "    - One-Hot Encoding\n",
    "    - Хэширование признаков (Hashing trick)\n",
    "- Vowpal Wabbit\n",
    "    - Новости. Бинарная классификация\n",
    "    - Письма. Многоклассовая классификация\n",
    "    - Рецензии к фильмам IMDB\n",
    "    - Классификация вопросов на Stackoverflow "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вначале импортируем сразу все нужные библиотеки"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import warnings\n",
    "\n",
    "warnings.filterwarnings(\"ignore\")\n",
    "import os\n",
    "import re\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from scipy.sparse import csr_matrix\n",
    "from sklearn.datasets import fetch_20newsgroups, load_files\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.metrics import (\n",
    "    accuracy_score,\n",
    "    classification_report,\n",
    "    confusion_matrix,\n",
    "    roc_auc_score,\n",
    "    roc_curve,\n",
    ")\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.preprocessing import LabelEncoder, OneHotEncoder\n",
    "\n",
    "%matplotlib inline\n",
    "import seaborn as sns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Стохастический градиентный спуск и онлайн-подход к обучению\n",
    "## Стохастический градиентный спуск\n",
    "\n",
    "Несмотря на то, что градиентный спуск – одна из первых тем, изучаемых в теории оптимизации и машинном обучении, сложно переоценить важность одной его модификации – стохастического градиентного спуска, который мы часто будем называть просто SGD (Stochastic Gradient Descent). \n",
    "\n",
    "Напомним, что суть градиентного спуска – минимизировать функцию, делая небольшие шаги в сторону наискорейшего убывания функции. Название методу подарил тот факт из математического анализа, что вектор $\\nabla f = (\\frac{\\partial f}{\\partial x_1}, \\ldots \\frac{\\partial f}{\\partial x_n})^T$ частных производных функции $f(x) = f(x_1, \\ldots x_n)$ задает направление наискорейшего возрастания этой функции. Значит, двигаясь в сторону антиградиента функции (вектора, противоположного градиенту), можно уменьшать ее значение быстрее всего. \n",
    "\n",
    "<img src='../../img/snowboard.jpg' width=70%>\n",
    "\n",
    "Это я в Шерегеше – всем катающим советую хотя бы раз в жизни там оказаться. Картинка для успокоения глаз, но с ее помощью можно пояснить интуицию градиентного спуска. Если задача – как можно быстрее спуститься с горы на сноуборде, то нужно в каждой точке выбирать максимальный уклон (если это совместимо с жизнью). Вычисление антиградиента – это и есть оценка крутизны склона в данной точке. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример**\n",
    "\n",
    "Задачу простой парной регрессии можно решать с помощью градиентного спуска. Предположим, мы прогнозируем одну переменную по другой – рост по весу – и постулируем линейную зависимость роста от веса."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import pandas as pd\n",
    "import seaborn as sns\n",
    "from matplotlib import pyplot as plt\n",
    "\n",
    "data_demo = pd.read_csv(\"../../data/weights_heights.csv\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.scatter(data_demo[\"Weight\"], data_demo[\"Height\"])\n",
    "plt.xlabel(\"Вес в фунтах\")\n",
    "plt.ylabel(\"Рост в дюймах\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Даны вектор $x$ длины $\\ell$– значения веса для каждого наблюдения (человека) и $y$ – вектор значений роста для каждого наблюдения (человека).\n",
    "\n",
    "Задача: найти такие веса $w_0$ и $w_1$, чтобы при прогнозе роста по весу в виде $y_i = w_0 + w_1 x_i$ (где $y_i$ – $i$-ое значение роста, $x_i$ –  $i$-ое значение веса) минимизировать квадратичную ошибку (можно и среднеквадратичную, но константа $\\frac{1}{\\ell}$ погоды не делает, а $\\frac{1}{2}$ заведена для красоты):\n",
    "$$SE(w_0, w_1) = \\frac{1}{2}\\sum_{i=1}^\\ell(y_i - (w_0 + w_1x_{i}))^2 \\rightarrow min_{w_0,w_1}$$\n",
    "\n",
    "Делать мы это будем с помощью градиентного спуска, посчитав частные производные функции $SE(w_0, w_1)$ по весам в модели – $w_0$ и $w_1$.\n",
    "Итеративная процедура обучения будет задаваться простыми формулами обновления весов (меняем веса так, чтобы длать небольшой, пропорционально малой константе $\\eta$, шаг в сторону антиградиента функции):\n",
    "\n",
    "$$\\begin{array}{rcl} w_0^{(t+1)} = w_0^{(t)} -\\eta \\frac{\\partial SE}{\\partial w_0} |_{t} \\\\  w_1^{(t+1)} = w_1^{(t)} -\\eta \\frac{\\partial SE}{\\partial w_1} |_{t} \\end{array}$$\n",
    "\n",
    "Если обратиться к ручке и бумажке и найти аналитические выражения для частных производных, то получим \n",
    "\n",
    "$$\\begin{array}{rcl} w_0^{(t+1)} = w_0^{(t)} + \\eta \\sum_{i=1}^{\\ell}(y_i - w_0^{(t)} - w_1^{(t)}x_i) \\\\  w_1^{(t+1)} = w_1^{(t)} + \\eta \\sum_{i=1}^{\\ell}(y_i - w_0^{(t)} - w_1^{(t)}x_i)x_i \\end{array}$$\n",
    "\n",
    "И все это довольно хорошо работает (в этой статье мы не будем обсуждать проблемы локальных минимумов, подбора шага градиентного спуска, момент и т.д. – про это и так много написано, можно обратиться к [главе](http://www.deeplearningbook.org/contents/numerical.html) \"Numeric Computation\" книги \"Deep Learning\") пока данных не становится слишком много. Проблема такого подхода в том, что вычисление градиента сводится к суммированию некоторых величин для каждого объекта обучающей выборки. То есть попросту, проблема в том, что итераций алгоритму на практике требуется много, а на каждой итерации веса пересчитываются по формуле, в которой есть сумма по всей выборке вида $\\sum_{i=1}^\\ell$. А что если объектов в выборке миллионы и миллиарды?\n",
    "\n",
    "\n",
    "\n",
    "Суть стохастического градиентного спуска – неформально, выкинуть знак суммы из формул пересчета весов и обновлять их по одному объекту. То есть в нашем случае\n",
    "\n",
    "$$\\begin{array}{rcl} w_0^{(t+1)} = w_0^{(t)} + \\eta (y_i - w_0^{(t)} - w_1^{(t)}x_i) \\\\  w_1^{(t+1)} = w_1^{(t)} + \\eta (y_i - w_0^{(t)} - w_1^{(t)}x_i)x_i \\end{array}$$\n",
    "\n",
    "При таком подходе на каждой итерации уже совсем не гарантировано движение в сторону наискорейшего убывания функции, и итераций может понадобиться на пару порядков больше, чем при обычном градиентном спуске. Зато пересчет весов на каждой итерации делается почти мгновенно. \n",
    "\n",
    "В качестве иллюстрации возьмем картинку Эндрю Ына из его [курса](https://www.coursera.org/learn/machine-learning) машинного обучения.\n",
    "\n",
    "<img src='../../img/sgd_convergence.png'>\n",
    "\n",
    "Нарисованы линии уровня некоторой функции, минимум который мы ищем. Красная кривая изображает изменение весов (на картинке $\\theta_0$ и $\\theta_1$ соответсвуют $w_0$ и $w_1$ в нашем примере). По свойствам градиента направление изменения в каждой точке будет перпендикулярно линиям уровня. При стохастическом подходе на каждой итерации веса меняется менее предсказуемо, порой даже кажется, что некоторые шаги неудачны – уводят от заветного минимума, но в итоге обе процедуры сходятся примерно к одному решению.\n",
    "\n",
    "Сходимость стохатического градиентного спуска к тому же решению, что и у градиентного спуска, является одним из важнейших фактов, доказанных в теории оптимизации. Сейчас в эпоху Deep Data и Big Learning чаще даже градиентным спуском называет именно его стохастическую версию."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Онлайн-подход к обучению\n",
    "Стохастический градиентный спуск, будучи одним из методов оптимизации, дает вполне практическое руководство к обучению алгоритмов классификации и регрессии на больших выборках – до сотен гигабайт (в зависимости от имеющейся памяти).\n",
    "\n",
    "В случае парной регрессии, который мы рассмотрели, на диске можно хранить обучающую выборку $(X,y)$ и, не загружая ее в оперативную память (она может попросту не поместиться), считывать объекты по одному и обновлять веса:\n",
    "\n",
    "$$\\begin{array}{rcl} w_0^{(t+1)} = w_0^{(t)} + \\eta (y_i - w_0^{(t)} - w_1^{(t)}x_i) \\\\  w_1^{(t+1)} = w_1^{(t)} + \\eta (y_i - w_0^{(t)} - w_1^{(t)}x_i)x_i \\end{array}$$\n",
    "\n",
    "После обработки всех объектов обучающей выборки, функционал, который мы оптимизируем (квадратичная ошибка в задаче регрессии или, напрмиер, логистическая – в задаче классификации) снизится, но часто нужно несколько десятков проходов по выборке, чтобы он снизился достаточно. \n",
    "\n",
    "Такой подход к обучению моделей часто называют онлайн-обучением, термин появился еще до того, как MOOC-и стали мэйнстримом.\n",
    "\n",
    "<img src=\"../../img/andrew_ng_online_learning.jpg\" width=50%>\n",
    "\n",
    "В этой статье мы не рассматриваем многих нюансов стохастической оптимизации (вот хорошая [статья](https://habrahabr.ru/post/318970/) на Хабре, фундаментально изучить эту тему можно по книге Boyd \"Convex Optimization\"), перейдем скорее к библиотеке Vowpal Wabbit, с помощью которой можно обучать простые модели на огромных выборках за счет стохастической оптимизации и еще одного трюка – хэширования признаков, о котором пойдет речь далее."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В библиотеке Scikit-learn классификаторы и регрессоры, обучаемые стохастическим градиентным спуском, реализованы классами `SGDClassifier` и `SGDRegressor` из `sklearn.linear_model`. Частью домашнего задания будет разобраться в них уже после собственной реализации этих простых онлайн-алгоритмов."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Работа с категориальными признаками: Label Encoding, One-Hot Encoding, Hashing trick\n",
    "\n",
    "## Label Encoding\n",
    "Подавляющее большинство методов классификации и регрессии сформулированы в терминах евклидовых или метрических пространств, то есть подразумевают представление данных в виде вещественных векторов одинаковой размерности. В реальных данных, однако, не так редки категориальные признаки, принимающие дискретные значения, такие как да/нет или  январь/февраль/.../декабрь. Обсудим то, как работать с такими данными, в частности с помощью линейных моделей, и что делать, если категориальных признаков много, да еще и у каждого куча уникальных значений. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рассмотрим выборку UCI bank, в которой большая часть признаков – категориальные."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.read_csv(\"../../data/bank_train.csv\")\n",
    "labels = pd.read_csv(\"../../data/bank_train_target.csv\", header=None)\n",
    "\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Нетрудно заметить, что достаточно много признаков в этом наборе данных не представлены числами. В таком виде данные еще нам не подходят - мы не сможем применять подавляющее большинство доступных нам методов.\n",
    "\n",
    "Чтобы найти решение, давайте рассмотрим признак education:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df[\"education\"].value_counts().plot.barh();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Естественным решением такой проблемы было бы однозначное отображение каждого значения в уникальное число. К примеру, мы могли бы преобразовать `university.degree` в 0, а `basic.9y` в 1. Эту простую операцию приходится делать часто, поэтому в модуле `preprocessing` библиотеки `sklearn` именно для этой задачи реализован класс `LabelEncoder`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "label_encoder = LabelEncoder()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Метод `fit` этого класса находит все уникальные значения и строит таблицу для соответствия каждой категории некоторому числу, а метод `transform` непосредственно преобразует значения в числа. После `fit` у `label_encoder` будет доступно поле `classes_`, содержащее все уникальные значения. Пронумеруем их, чтобы убедиться, что преобразование выполнено верно. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mapped_education = pd.Series(label_encoder.fit_transform(df[\"education\"]))\n",
    "mapped_education.value_counts().plot.barh()\n",
    "print(dict(enumerate(label_encoder.classes_)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Что произойдет, если у нас появятся данные с другими категориями?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "try:\n",
    "    label_encoder.transform(df[\"education\"].replace(\"high.school\", \"high_school\"))\n",
    "except Exception as e:\n",
    "    print(\"Error:\", e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Таким образом, при использовании этого подхода мы всегда должны быть уверены, что признак не может принимать неизвестных ранее значений. К этой проблеме мы вернемся чуть позже, а сейчас заменим весь столбец education на преобразованный:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df[\"education\"] = mapped_education\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Продолжим преобразование для всех столбцов, имеющих тип `object` – именно этот тип задается в pandas для таких данных."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "categorical_columns = df.columns[df.dtypes == \"object\"].union([\"education\"])\n",
    "for column in categorical_columns:\n",
    "    df[column] = label_encoder.fit_transform(df[column])\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Основная проблема такого представления заключается в том, что числовой код создал евклидово представление для данных.\n",
    "\n",
    "К примеру, нами неявным образом была введена алгебра над значениями работы - мы можем вычесть работу клиента 1 из работы клиента 2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.loc[1].job - df.loc[2].job"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Конечно же, эта операция не имеет никакого смысла. Но именно на этом основаны метрики близости объектов, что делает бессмысленным применение метода ближайшего соседа на данных в таком виде. Аналогичным образом, никакого смысла не будет иметь применение линейных моделей. Убедимся в этом:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def logistic_regression_accuracy_on(dataframe, labels):\n",
    "    features = dataframe.as_matrix()\n",
    "    train_features, test_features, train_labels, test_labels = train_test_split(\n",
    "        features, labels\n",
    "    )\n",
    "\n",
    "    logit = LogisticRegression()\n",
    "    logit.fit(train_features, train_labels)\n",
    "    return classification_report(test_labels, logit.predict(test_features))\n",
    "\n",
    "\n",
    "print(logistic_regression_accuracy_on(df[categorical_columns], labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для того, чтобы мы смогли применять линейные модели на таких данных нам необходим другой метод, который называется One-Hot Encoding\n",
    "\n",
    "## One-Hot Encoding\n",
    "\n",
    "Предположим, что некоторый признак может принимать 10 разных значений. В этом случае one hot encoding подразумевает создание 10 признаков, все из которых равны нулю *за исключением одного*. На позицию, соответствующую численному значению признака мы помещаем 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "one_hot_example = pd.DataFrame([{i: 0 for i in range(10)}])\n",
    "one_hot_example.loc[0, 6] = 1\n",
    "one_hot_example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Эта техника реализована в `sklearn.preprocessing` в классе `OneHotEncoder`. По умолчанию `OneHotEncoder` преобразует данные в разреженную матрицу, чтобы не расходовать память на хранение многочисленных нулей. Однако в этом примере размер данных не является для нас проблемой, поэтому мы будем использовать \"плотное\" представление."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "onehot_encoder = OneHotEncoder(sparse=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "encoded_categorical_columns = pd.DataFrame(\n",
    "    onehot_encoder.fit_transform(df[categorical_columns])\n",
    ")\n",
    "encoded_categorical_columns.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мы получили 53 столбца - именно столько различных уникальных значений могут принимать категориальные столбцы исходной выборки. Преобразованные с помощью One-Hot Encoding данные начинают обретать смысл для линейной модели:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(logistic_regression_accuracy_on(encoded_categorical_columns, labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Хэширование признаков (Hashing trick)\n",
    "Реальные данные могут оказаться гораздо более динамичными, и мы не всегда можем рассчитывать, что категориальные признаки не будут принимать новых значений. Все это сильно затрудняет использование уже обученных моделей на новых данных. Кроме того, `LabelEncoder` подразумевает предварительный анализ всей выборки и хранение построенных отображений в памяти, что затрудняет работу в режиме больших данных.\n",
    "\n",
    "Для решения этих проблем существует более простой подход к векторизации категориальных признаков, основанный на хэшировании, известный как hashing trick. \n",
    "\n",
    "Хэш-функции могут помочь нам в задаче поиска уникальных кодов для различных значений признака, к примеру:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for s in (\"university.degree\", \"high.school\", \"illiterate\"):\n",
    "    print(s, \"->\", hash(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Отрицательные и настолько большие по модулю значения нам не подойдут. Ограничим область значений хэш-функции:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hash_space = 25\n",
    "for s in (\"university.degree\", \"high.school\", \"illiterate\"):\n",
    "    print(s, \"->\", hash(s) % hash_space)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Представим, что у нас в выборке есть холостой студент, которому позвонили в понедельник, тогда его вектор признаков будет сформирован аналогично One-Hot Encoding, но в едином пространстве фиксированного размера для всех признаков:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hashing_example = pd.DataFrame([{i: 0.0 for i in range(hash_space)}])\n",
    "for s in (\"job=student\", \"marital=single\", \"day_of_week=mon\"):\n",
    "    print(s, \"->\", hash(s) % hash_space)\n",
    "    hashing_example.loc[0, hash(s) % hash_space] = 1\n",
    "hashing_example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стоит обратить внимание, что в этом примере хэшировались не только значения признаков, а пары **название признака + значение признака**. Это необходимо, чтобы разделить одинаковые значения разных признаков между собой, к примеру:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert hash(\"no\") == hash(\"no\")\n",
    "assert hash(\"housing=no\") != hash(\"loan=no\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Может ли произойти коллизия хэш-функции, то есть совпадение кодов для двух разных значений? Нетрудно доказать, что при достаточном размере пространства хэширования это происходит редко, но даже в тех случаях, когда это происходит, это не будет приводить к существенному ухудшению качества классификации или регрессии.\n",
    "\n",
    "Возможно, вы спросите: \"а что за хрень вообще происходит?\", и покажется, что при хэшировании признаков страдает здравый смысл. Возможно, но эта эвристика – по сути, единственный подход к тому, чтобы работать с категориальными признаками, у которых много уникальных значений. Более того, эта техника себя хорошо зарекомендовала по результатами на практике. Подробней про хэширование признаков (learning to hash) можно почитать в [этом](https://arxiv.org/abs/1509.05472) обзоре, а также в [материалах](https://github.com/esokolov/ml-course-hse/blob/master/2016-fall/lecture-notes/lecture06-linclass.pdf) Евгения Соколова."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Библиотека Vowpal Wabbit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vowpal Wabbit (VW) является одной из наиболее широко используемых библиотек в индустрии. Её отличает высокая скорость работы и поддержка большого количества различных режимов обучения. Особый интерес для больших и высокоразмерных данных представляет онлайн-обучение  – самая сильная сторона библиотеки. \n",
    "Также реализовано хэширование признаков, и Vowpal Wabbit отлично подходит для работы с текстовыми данными.\n",
    "\n",
    "Основным интерфейсом для работы с VW является shell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!vw --help"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Vowpal Wabbit считывает данные из файла или стандартного ввода (stdin) в формате, который имеет следующий вид:\n",
    "\n",
    "`[Label] [Importance] [Tag]|Namespace Features |Namespace Features ... |Namespace Features`\n",
    "\n",
    "`Namespace=String[:Value]`\n",
    "\n",
    "`Features=(String[:Value] )*`\n",
    "\n",
    "где [] обозначает необязательные элементы, а (...)\\* означает повтор неопределенное число раз. \n",
    "\n",
    "- **Label** является числом, \"правильным\" ответом. В случае классификации обычно принимает значение 1/-1, а в случае регрессии некоторое вещественное число\n",
    "- **Importance** является числом и отвечает за вес примера при обучении. Это позволяет бороться с проблемой несбалансированных данных, изученной нами ранее\n",
    "- **Tag** является некоторой строкой без пробелов и отвечает за некоторое \"название\" примера, которое сохраняется при предсказании ответа. Для того, чтобы отделить Tag от Importance лучше начинать Tag с символа '.\n",
    "- **Namespace** служит для создания отдельных пространств признаков. В аргументах Namespace именуются по первой букве, это нужно учитывать при выборе их названий\n",
    "- **Features** являются непосредственно признаками объекта внутри **Namespace**. Признаки по умолчанию имеют вес 1.0, но его можно переопределить, к примеру feature:0.1. \n",
    "\n",
    "\n",
    "К примеру, под такой формат подходит следующая строка:\n",
    "\n",
    "```\n",
    "1 1.0 |Subject WHAT car is this |Organization University of Maryland:0.5 College Park\n",
    "```\n",
    "\n",
    "\n",
    "чтобы убедиться в этом, запустим vw с этим обучающим примером:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "! echo '1 1.0 |Subject WHAT car is this |Organization University of Maryland:0.5 College Park' | vw"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "VW является прекрасным инструментом для работы с текстовыми данными. Убедимся в этом с помощью выборки 20newsgroups, содержащей письма из 20 различных тематических рассылок.\n",
    "\n",
    "\n",
    "## Новости. Бинарная классификация"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "newsgroups = fetch_20newsgroups(\"../../data/news_data\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "newsgroups[\"target_names\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рассмотрим первый текстовый документ этой коллекции:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "text = newsgroups[\"data\"][0]\n",
    "target = newsgroups[\"target_names\"][newsgroups[\"target\"][0]]\n",
    "\n",
    "print(\"-----\")\n",
    "print(target)\n",
    "print(\"-----\")\n",
    "print(text.strip())\n",
    "print(\"----\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Приведем данные к формату Vowpal Wabbit, при этом оставляя только слова не короче 3 символов. Здесь мы не выполняем многие важные в анализе текстов процедуры (стемминг и лемматизацию), но, как увидим, задача и так будет решаться хорошо."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_vw_format(document, label=None):\n",
    "    return (\n",
    "        str(label or \"\")\n",
    "        + \" |text \"\n",
    "        + \" \".join(re.findall(\"\\w{3,}\", document.lower()))\n",
    "        + \"\\n\"\n",
    "    )\n",
    "\n",
    "\n",
    "to_vw_format(text, 1 if target == \"rec.autos\" else -1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Разобьем выборку на обучающую и тестовую и запишем в файл преобразованные таким образом документы. Будем считать документ положительным, если он относится к рассылке про автомобили **rec.autos**. Так мы построим модель, отличающую письма про автомобили от остальных: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_documents = newsgroups[\"data\"]\n",
    "all_targets = [\n",
    "    1 if newsgroups[\"target_names\"][target] == \"rec.autos\" else -1\n",
    "    for target in newsgroups[\"target\"]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_documents, test_documents, train_labels, test_labels = train_test_split(\n",
    "    all_documents, all_targets, random_state=7\n",
    ")\n",
    "\n",
    "with open(\"../../data/news_data/20news_train.vw\", \"w\") as vw_train_data:\n",
    "    for text, target in zip(train_documents, train_labels):\n",
    "        vw_train_data.write(to_vw_format(text, target))\n",
    "with open(\"../../data/news_data/20news_test.vw\", \"w\") as vw_test_data:\n",
    "    for text in test_documents:\n",
    "        vw_test_data.write(to_vw_format(text))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Запустим Vowpal Wabbit на сформированном файле. Мы решаем задачу классификации, поэтому зададим функцию потерь в значение hinge (линейный SVM). Построенную модель мы сохраним в соответствующий файл `20news_model.vw`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!vw -d ../../data/news_data/20news_train.vw \\\n",
    "  --loss_function hinge -f ../../data/news_data/20news_model.vw"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Модель обучена. VW выводит достаточно много полезной информации по ходу обучения (тем не менее, ее можно погасить, если задать параметр --quiet). Подробно вывод диагностическйой информации разобран в документации VW на GitHub – [тут](https://github.com/JohnLangford/vowpal_wabbit/wiki/Tutorial#vws-diagnostic-information). Обратите внимание, что average loss снижался по ходу выполнения итераций. Для вычисления функции потерь VW использует еще не просмотренные примеры, поэтому, как правило, эта оценка является корректной. Применим обученную модель на тестовой выборке, сохраняя предсказания в файл с помощью опции -p: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!vw -i ../../data/news_data/20news_model.vw -t -d ../../data/news_data/20news_test.vw \\\n",
    "-p ../../data/news_data/20news_test_predictions.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Загрузим полученные предсказания, вычислим AUC и отобразим ROC-кривую:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"../../data/news_data/20news_test_predictions.txt\") as pred_file:\n",
    "    test_prediction = [float(label) for label in pred_file.readlines()]\n",
    "\n",
    "auc = roc_auc_score(test_labels, test_prediction)\n",
    "roc_curve = roc_curve(test_labels, test_prediction)\n",
    "\n",
    "with plt.xkcd():\n",
    "    plt.plot(roc_curve[0], roc_curve[1])\n",
    "    plt.plot([0, 1], [0, 1])\n",
    "    plt.xlabel(\"FPR\")\n",
    "    plt.ylabel(\"TPR\")\n",
    "    plt.title(\"test AUC = %f\" % (auc))\n",
    "    plt.axis([-0.05, 1.05, -0.05, 1.05]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Полученное значения AUC говорит о высоком качестве классификации."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Новости. Многоклассовая классификация"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Используем ту же выборку, что в прошлой части, но решаем задачу многоклассовой классификации. Тут `Vowpal Wabbit` слегка капризничает – он любит, чтоб метки классов были распределены от 1 до K, где K – число классов в задаче классификации (в нашем случае – 20). Поэтому придется применить LabelEncoder, да еще и +1 потом добавить (`LabelEncoder` переводит метки в диапозон от 0 до K-1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_documents = newsgroups[\"data\"]\n",
    "topic_encoder = LabelEncoder()\n",
    "all_targets_mult = topic_encoder.fit_transform(newsgroups[\"target\"]) + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Выборки будут те же, а метки поменяются, train_labels_mult и test_labels_mult – векторы меток от 1 до 20.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_documents, test_documents, train_labels_mult, test_labels_mult = train_test_split(\n",
    "    all_documents, all_targets_mult, random_state=7\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"../../data/news_data/20news_train_mult.vw\", \"w\") as vw_train_data:\n",
    "    for text, target in zip(train_documents, train_labels_mult):\n",
    "        vw_train_data.write(to_vw_format(text, target))\n",
    "with open(\"../../data/news_data/20news_test_mult.vw\", \"w\") as vw_test_data:\n",
    "    for text in test_documents:\n",
    "        vw_test_data.write(to_vw_format(text))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обучим Vowpal Wabbit в режиме многоклассовой классификации, передав параметр `oaa` (от \"one against all\"), равный числу классов. Также перечислим параметры, которые можно понастраивать, и от которых качество модели может довольно значительно зависеть (более полно – в официальном [тьюториале](https://github.com/JohnLangford/vowpal_wabbit/wiki/Tutorial) по Vowpal Wabbit):\n",
    " - темп обучения (-l, по умолчанию 0.5) – коэффициент перед изменением весов модели при каждом изменении\n",
    " - степень убывания темпа обучения (--power_t, по умолчанию 0.5) – на практике проверено, что если темп обучения уменьшается при увеличении числа итераций стохастического градиентного спуска, то минимум функции находится лучше \n",
    " - функция потерь (--loss_function) – от нее, по сути, зависит обучаемый алгоритм. Про функции потерь в [документации](https://github.com/JohnLangford/vowpal_wabbit/wiki/Loss-functions)\n",
    " - регуляризация (-l1) – тут надо обратить внимание на то, что в VW регуляризация считается для каждого объекта, поэтому коэффициенты регуляризации обычно берутся малыми, около $10^{-20}.$\n",
    " \n",
    " Дополнительно можно попробовать автоматическую настройку параметров Vowpal Wabbit с Hyperopt. Пока это работает только с Python 2. [Статья](https://habrahabr.ru/company/dca/blog/272697/) на Хабре."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "!vw --oaa 20 ../../data/news_data/20news_train_mult.vw \\\n",
    "-f ../../data/news_data/20news_model_mult.vw --loss_function=hinge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "!vw -i ../../data/news_data/20news_model_mult.vw -t \\\n",
    "-d ../../data/news_data/20news_test_mult.vw \\\n",
    "-p ../../data/news_data/20news_test_predictions_mult.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"../../data/news_data/20news_test_predictions_mult.txt\") as pred_file:\n",
    "    test_prediction_mult = [float(label) for label in pred_file.readlines()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "accuracy_score(test_labels_mult, test_prediction_mult)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В качестве примера анализа резльтатов, посмотрим, с какими темами классификатор путает атеизм."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = confusion_matrix(test_labels_mult, test_prediction_mult)\n",
    "for i in np.where(M[0, :] > 0)[0][1:]:\n",
    "    print(\n",
    "        newsgroups[\"target_names\"][i], M[0, i],\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Рецензии к фильмам IMDB"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этой части мы будем заниматься бинарной классификацией отзывов к фильмам, публикованным на сайте IMDB. Обратите внимание, насколько быстро будет работать Vowpal Wabbit.\n",
    "\n",
    "Используем функцию `load_files` из `sklearn.datasets` для загрузки отзывов по фильмам [отсюда](https://drive.google.com/file/d/1xq4l5c0JrcxJdyBwJWvy0u9Ad_pvkJ1l/view?usp=sharing). Скачайте данные и укажите свой путь к каталогу `imdb_reviews` (в нем должны быть каталоги *train* и *test*). Разархивирование может занять несколько минут – там 100 тыс. файлов. В обучающей и тестовой выборках по 12500 тысяч хороших и плохих отзывов к фильмам. Отделим данные (собственно, тексты) от меток."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# поменяйте на свой путь\n",
    "path_to_movies = \"/Users/y.kashnitsky/Yandex.Disk.localized/ML/data/imdb_reviews/\"\n",
    "reviews_train = load_files(os.path.join(path_to_movies, \"train\"))\n",
    "text_train, y_train = reviews_train.data, reviews_train.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Number of documents in training data: %d\" % len(text_train))\n",
    "print(np.bincount(y_train))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "То же самое с тестовой выборкой."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "reviews_test = load_files(os.path.join(path_to_movies, \"test\"))\n",
    "text_test, y_test = reviews_test.data, reviews_train.target\n",
    "print(\"Number of documents in test data: %d\" % len(text_test))\n",
    "print(np.bincount(y_test))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Примеры отзывов и соответствующих меток"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "text_train[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_train[0]  # хороший отзыв"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "text_train[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_train[1]  # плохой отзыв"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Будем использовать ранее написанную функцию `to_vw_format`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "to_vw_format(str(text_train[1]), 1 if y_train[0] == 1 else -1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Подготовим обучающую (`movie_reviews_train.vw`), отложенную (`movie_reviews_valid.vw`) и тестовую (`movie_reviews_test.vw`) выборки для Vowpal Wabbit. 70% исходной обучаюшей выборки оставим под обучение, 30% – под отложенную выборку."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_share = int(0.7 * len(text_train))\n",
    "train, valid = text_train[:train_share], text_train[train_share:]\n",
    "train_labels, valid_labels = y_train[:train_share], y_train[train_share:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(train_labels), len(valid_labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"../../data/movie_reviews_train.vw\", \"w\") as vw_train_data:\n",
    "    for text, target in zip(train, train_labels):\n",
    "        vw_train_data.write(to_vw_format(str(text), 1 if target == 1 else -1))\n",
    "with open(\"../../data/movie_reviews_valid.vw\", \"w\") as vw_train_data:\n",
    "    for text, target in zip(valid, valid_labels):\n",
    "        vw_train_data.write(to_vw_format(str(text), 1 if target == 1 else -1))\n",
    "with open(\"../../data/movie_reviews_test.vw\", \"w\") as vw_test_data:\n",
    "    for text in text_test:\n",
    "        vw_test_data.write(to_vw_format(str(text)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!head -2 ../../data/movie_reviews_train.vw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!head -2 ../../data/movie_reviews_valid.vw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!head -2 ../../data/movie_reviews_test.vw"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Обучим модель Vowpal Wabbit со следующими агрументами:**\n",
    "\n",
    " - -d, путь к обучающей выборке (соотв. файл .vw )\n",
    " - --loss_function – hinge (хотя можно и поэкспериментировать с другими)\n",
    " - -f – путь к файлу, в который запишется модель (можно тоже в формате .vw)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!vw -d ../../data/movie_reviews_train.vw \\\n",
    "--loss_function hinge -f movie_reviews_model.vw --quiet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сделаем прогноз для отложенной выборки с помощью обученной модели Vowpal Wabbit, передав следующие аргументы:\n",
    " - -i –путь к обученной модели (соотв. файл .vw)\n",
    " - -t -d – путь к отложенной выборке (соотв. файл .vw)\n",
    " - -p – путь к txt-файлу, куда запишутся прогнозы"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!vw -i movie_reviews_model.vw -t -d ../../data/movie_reviews_valid.vw \\\n",
    "-p movie_valid_pred.txt --quiet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Считаем прогноз из файла и посчитаем долю правильных ответов и ROC AUC. Учтем, что VW выводит оценки вероятности принадлежности к классу +1. Эти оценки распределены на [-1, 1], поэтому бинарным ответом алгоритма (0 или 1) будем попросту считать тот факт, что оценка получилась положительной."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"movie_valid_pred.txt\") as pred_file:\n",
    "    valid_prediction = [float(label) for label in pred_file.readlines()]\n",
    "print(\n",
    "    \"Accuracy: {}\".format(\n",
    "        round(\n",
    "            accuracy_score(\n",
    "                valid_labels, [int(pred_prob > 0) for pred_prob in valid_prediction]\n",
    "            ),\n",
    "            3,\n",
    "        )\n",
    "    )\n",
    ")\n",
    "print(\"AUC: {}\".format(round(roc_auc_score(valid_labels, valid_prediction), 3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Сделаем то же самое для тестовой выборки."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!vw -i movie_reviews_model.vw -t -d ../../data/movie_reviews_test.vw \\\n",
    "-p movie_test_pred.txt --quiet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"movie_test_pred.txt\") as pred_file:\n",
    "    test_prediction = [float(label) for label in pred_file.readlines()]\n",
    "print(\n",
    "    \"Accuracy: {}\".format(\n",
    "        round(\n",
    "            accuracy_score(\n",
    "                y_test, [int(pred_prob > 0) for pred_prob in test_prediction]\n",
    "            ),\n",
    "            3,\n",
    "        )\n",
    "    )\n",
    ")\n",
    "print(\"AUC: {}\".format(round(roc_auc_score(y_test, test_prediction), 3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Попробуем улучшить прогноз за счет задействования биграмм"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!vw -d ../../data/movie_reviews_train.vw \\\n",
    "--loss_function hinge --ngram 2 -f movie_reviews_model2.vw --quiet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!vw -i movie_reviews_model2.vw -t -d ../../data/movie_reviews_valid.vw \\\n",
    "-p movie_valid_pred2.txt --quiet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"movie_valid_pred2.txt\") as pred_file:\n",
    "    valid_prediction = [float(label) for label in pred_file.readlines()]\n",
    "print(\n",
    "    \"Accuracy: {}\".format(\n",
    "        round(\n",
    "            accuracy_score(\n",
    "                valid_labels, [int(pred_prob > 0) for pred_prob in valid_prediction]\n",
    "            ),\n",
    "            3,\n",
    "        )\n",
    "    )\n",
    ")\n",
    "print(\"AUC: {}\".format(round(roc_auc_score(valid_labels, valid_prediction), 3)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!vw -i movie_reviews_model2.vw -t -d ../../data/movie_reviews_test.vw \\\n",
    "-p movie_test_pred2.txt --quiet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"movie_test_pred2.txt\") as pred_file:\n",
    "    test_prediction2 = [float(label) for label in pred_file.readlines()]\n",
    "print(\n",
    "    \"Accuracy: {}\".format(\n",
    "        round(\n",
    "            accuracy_score(\n",
    "                y_test, [int(pred_prob > 0) for pred_prob in test_prediction2]\n",
    "            ),\n",
    "            3,\n",
    "        )\n",
    "    )\n",
    ")\n",
    "print(\"AUC: {}\".format(round(roc_auc_score(y_test, test_prediction2), 3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Видим, что биграммы помогли повысить качество классификации."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Классификация вопросов на StackOverflow "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь посмотрим, как в действительности Vowpal Wabbit справляется с большими выборками. Имеются 10 Гб вопросов со StackOverflow – [ссылка](https://disk.yandex.ru/d/1iJxJqlNKiXH0A) на данные, там 7.5 миллионов вопросов, и у каждого вопроса может быть несколько тегов. Данные довольно чистые, и не называйте это бигдатой даже в пабе :)\n",
    "\n",
    "<img src='../../img/say_big_data.jpg' width=50%>\n",
    "\n",
    "Из всех тегов выделены 10, и решается задача классификации на 10 классов: по тексту вопроса надо поставить один из 10 тегов, соответствующих 10 популярным языкам программирования. Предобработанные данные не даются, поскольку их надо получить в домашней работе."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# поменяйте путь к данным\n",
    "PATH_TO_DATA = \"/Users/y.kashnitsky/Documents/Machine_learning/org_mlcourse_open/private/stackoverflow_hw/\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!du -hs $PATH_TO_DATA/stackoverflow_*.vw"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вот как выглядят строки, на которых будет обучаться Vowpal Wabbit. 10 означает 10 класс, далее вертикальная черта и просто текст вопроса. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!head -1 $PATH_TO_DATA/stackoverflow_train.vw"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обучим на обучающей части выборки (3.3 Гб) модель Vowpal Wabbit со следующими аргументами: \n",
    "- -oaa 10 – указываем, что классификация на 10 классов \n",
    "- -d – путь к данным \n",
    "- -f – путь к модели, которая будет построена \n",
    "- -b 28 – используем 28 бит для хэширования, то есть признаковое пространство ограничено $2^{28}$ признаками, что в данном случае больше, чем число уникальных слов в выборке (но потом появятся би- и триграммы, и ограничение размерности признакового пространства начнет работать)\n",
    "- также указываем random seed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "!vw --oaa 10 -d $PATH_TO_DATA/stackoverflow_train.vw \\\n",
    "-f vw_model1.vw -b 28 --random_seed 17 --quiet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Заметим, что модель обучилась всего за 43 секунды, для тестовой выборки прогнозы сделала еще за 15 секунд, доля правильных ответов – почти 92%. Далее качество модели можно повышать за счет нескольких проходов по выборке, задействования биграмм и настройке параметров. Это вместе с предобработкой данных и будет второй частью домашнего задания."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "!vw -t -i vw_model1.vw \\\n",
    "-d $PATH_TO_DATA/stackoverflow_test.vw \\\n",
    "-p vw_valid_pred1.csv --random_seed 17 --quiet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "\n",
    "import numpy as np\n",
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "vw_pred = np.loadtxt(\"vw_valid_pred1.csv\")\n",
    "test_labels = np.loadtxt(\n",
    "    os.path.join(PATH_TO_DATA, \"stackoverflow_test_labels.txt\")\n",
    ")\n",
    "accuracy_score(test_labels, vw_pred)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Домашнее задание\n",
    "В этот раз задание будет большим. В первой части, чтоб вам не казалось, что Vowpal Wabbit – это какая-то магия, вы реализуете самостоятельно классификатор и регрессор, обучаемые стохастическим градиентным спуском.\n",
    "\n",
    "Во второй части вам предлагается взять набор данных (~ 7 Гб), содержащий вопросы на StackOverflow и теги этих вопросов, предобработать данные (подумав над эффективность совершаемых операций) и построить классификатор вопросов по 10 тегам (по 10 языкам программирования). Возможно, вы уже удивились, как простая модель VW может обучиться на такой выборке за секунды или минуты на простом железе, без всяких Hadoop-кластеров. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Полезные ссылки\n",
    "- материалы Евгения Соколова: [Многоклассовая классификация и категориальные признаки](https://github.com/esokolov/ml-course-hse/blob/master/2016-fall/lecture-notes/lecture06-linclass.pdf) (там же про хэширование признаков), [Линейная регрессия](https://github.com/esokolov/ml-course-hse/blob/master/2016-fall/lecture-notes/lecture02-linregr.pdf) (там же про градиентный спуск и его стохастическую версию), [презентация](https://github.com/esokolov/ml-course-msu/blob/master/ML15/lecture-notes/Sem08_vw.pdf) про Vowpal Wabbit\n",
    "- [Глава](http://www.deeplearningbook.org/contents/numerical.html) \"Numeric Computation\" книги \"Deep Learning\"\n",
    "- Обширная [документация](https://github.com/JohnLangford/vowpal_wabbit/wiki) Vowpal Wabbit на GitHub\n",
    "- Минималистичная [статья](https://habrahabr.ru/company/mlclass/blog/248779/) на Хабре про VW\n",
    "- [Статья](https://habrahabr.ru/company/dca/blog/272697/) на Хабре про связку VW и hyperopt "
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
